package com.zdp.leetcodeMiddle;

import java.util.ArrayList;
import java.util.List;

/*
* 题目描述：
* 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例:

输入: "aab"
输出:
[
  ["aa","b"],
  ["a","a","b"]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-partitioning
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 分割回文串_131 {
    public static void main(String[] args) {
        分割回文串_131 demo = new 分割回文串_131();
        List<List<String>> aab = demo.partition("aab");
        for(List<String> t :aab){
            System.out.println(t.toString());
        }
    }

    /*
    * 解题思路： 每次都获取一个
    * */
    private List<List<String>> result = new ArrayList<>();
    public List<List<String>> partition(String s) {
        f(new ArrayList<String>(),s,0);
        return result;
    }

    public void f(List<String> temp,String s,int index){
        if(index >= s.length()){
            result.add(new ArrayList<>(temp));
            return ;
        }

        for(int i = index; i < s.length(); i++){
            boolean flag = true;
            int end = i;
            int start = index;
            while(end < s.length() && start <= end){
                if( s.charAt(start) != s.charAt(end)){
                    flag =  false;
                    break;
                }
                start ++;
                end --;
            }
            if(flag){
                // 是一个回文串
                temp.add(s.substring(index,i+1));
                f(temp,s,i+1);
                // 回溯
                temp.remove(temp.size() - 1);
            }
        }

        return ;
    }
}
